package jalgebrava.group.groups;

import static jalgebrava.group.util.GroupMixins.*;
import static jalgebrava.util.collections.IterableMixins.*;
import jalgebrava.group.Group;
import jalgebrava.group.GroupElement;
import jalgebrava.group.Subset;
import jalgebrava.group.algorithms.general.MinimalGeneratingSubset;
import jalgebrava.group.morphisms.Automorphism;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import org.apache.log4j.Logger;

public final class AutomorphismGroupFactory {
	private final static Logger logger = Logger.getLogger(AutomorphismGroupFactory.class);
	private AutomorphismGroupFactory() {
		// hidden
	}
	
	public final static <G> Group<Automorphism<G>> mk(final Group<G> g) {
		Group<Automorphism<G>> result = null;
		
		if (result!=null) {
			return result;
		}
		Subset<G> mgs = MinimalGeneratingSubset.minimalGeneratingSubset(g);
		logger.debug("MGS = " + mgs);
		Set<Integer> ordersNeeded = new HashSet<Integer>(); 
		for (G x: mgs) {
			ordersNeeded.add(g.order(x));
		}
		Map<Integer, List<G>> candidates = new TreeMap<Integer, List<G>>();
		for (int i: ordersNeeded) {
			candidates.put(i, new ArrayList<G>());
		}
		for (GroupElement<G> x: elementsInDescendingOrder(g)) {
			int o = x.order();
			if (ordersNeeded.contains(o)) {
				candidates.get(o).add(x.g);
			}
		}
		int num = 1;
		for (G x: mgs) {
			int numC = candidates.get(g.order(x)).size();
			num *= numC;
			logger.trace(x + " -> " + candidates.get(g.order(x)).size());
		}
		logger.info("Worst case, we have to check " + num + " partial maps");
		Set<G> mgsClone = mgs.getCopyOfSet();
		final List<Automorphism<G>> automorphisms = new LinkedList<Automorphism<G>>();
		enumeratePartialMaps(g, mgsClone, candidates, new HashMap<G,G>(), automorphisms);
		result = new AbstractGroup<Automorphism<G>>("Aut("+g.getDescription()+")", asImmutable(automorphisms), automorphisms.size()) {

			@Override
			public boolean contains(Automorphism<G> x) {
				return automorphisms.contains(x);
			}

			@Override
			public Automorphism<G> inv(Automorphism<G> x) {
				return x.invert();
			}

			@Override
			public Automorphism<G> mul(Automorphism<G> x, Automorphism<G> y) {
				return x.multiply(y);
			}

			@Override
			public Automorphism<G> unit() {
				return Automorphism.identityAutomorphism(g);
			}
			
		};
		
		return result;
	}
	
	private static final <G> void enumeratePartialMaps(Group<G> g,
			Set<G> left, Map<Integer, List<G>> candidates, Map<G,G> partial, List<Automorphism<G>> collector) {
		
		if (left.isEmpty()) {
			logger.trace("Partial:" + partial);
			Automorphism<G> extended = Automorphism.extendPartialMap(g, partial);
			if (extended == null) {
				logger.trace("Failed to extend");
			} else {
				collector.add(extended);
				
			}
			return;
		}
		G x = left.iterator().next();
		left.remove(x);
		List<G> candidatesForX = candidates.get(g.order(x));
		
		for (G imageOfX : candidatesForX) {
			partial.put(x, imageOfX);
			enumeratePartialMaps(g, left, candidates, partial, collector);
		}
		left.add(x);
		
	}
	
}
